"""
     A --> B
     A --> C
     B --> C
     B --> D
     C --> D
     D --> C
     E --> F
     F --> C
"""


def find_path(graph, start, end, path=[]):
    # 寻找一条路径
    path = path + [start]
    if start == end:
        return path
    if start not in graph:
        return None
    for node in graph[start]:
        if node not in path:
            new_path = find_path(graph, node, end, path)
            if new_path:
                return new_path
    return path


def find_all_path(graph, start, end, path=[]):
    # 查找所有路径
    path = path + [start]
    if start == end:
        return path
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            new_paths = find_all_path(graph, node, end, path)
            for new_path in new_paths:
                paths.append(new_path)
    return paths


def find_shortest_path(graph, start, end, path=[]):
    # 查找最短路径
    path = path + [start]
    if start == end:
        return path
    if start not in graph:
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            new_path = find_shortest_path(graph, node, end, path)
            if new_path:
                if not shortest or len(new_path) < len(shortest):
                    shortest = new_path
    return shortest


if __name__ == '__main__':
    graph = {'A': ['B', 'C'],
             'B': ['C', 'D'],
             'C': ['D'],
             'D': ['C'],
             'E': ['F'],
             'F': ['C']}
    print(find_path(graph, 'A', 'D'))
    print(find_all_path(graph, 'A', 'D'))
    print(find_shortest_path(graph, 'A', 'D'))
